import java.util.HashMap;
import java.util.Map;

/**
 * @author SongJun
 * @description 最小覆盖子串(滑动窗口)
 * @date 2021/9/13 10:20
 */
public class MinimumWindowSubstring {
    public static void main(String[] args) {
        MinimumWindowSubstring instance = new MinimumWindowSubstring();
        String s = "ADOBECODEBANC";
        String t = "ABC";
        System.out.println(instance.minWindow(s, t));
    }

    public String minWindow(String s, String t) {
        int start = 0;
        int length = Integer.MAX_VALUE;
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        int valid = 0;
        int left=0, right = 0;
        for(int i=0; i<t.length(); i++){
            char c = t.charAt(i);
            need.put(c, need.containsKey(c) ? need.get(c)+1 : 1);
        }
        for(;right < s.length();){
            char c = s.charAt(right++);
            //右边界滑动
            if(need.containsKey(c)){
                window.put(c, window.containsKey(c) ? window.get(c)+1 : 1);
                if(need.get(c).equals(window.get(c))){
                    valid++;
                }
            }
            //左边界滑动
            while(valid >= need.size()){
                if(right - left < length){
                    start = left;
                    length = right - left;
                }
                char cl = s.charAt(left++);
                if(need.containsKey(cl)){
                    window.put(cl, window.get(cl) - 1);
                    if(window.get(cl) < need.get(cl)) {
                        valid--;
                    }
                }

            }
        }
        return length == Integer.MAX_VALUE ? "" : s.substring(start, start + length);
    }
}
